1. Technical Field
The present invention is directed to an improved method and apparatus for performing buffer insertion into an integrated circuit design. More specifically, the present invention is directed to a routing and buffer insertion technique that simultaneously performs blockage avoidance, delay optimization, and design density management.
2. Description of Related Art
It is now widely accepted that interconnect performance is becoming increasingly dominant over transistor and logic performance in the deep submicron regime. Buffer insertion is now a fundamental technology used in modern integrated circuit design methodologies. As gate delays decrease with increasing chip dimensions, however, the number of buffers required quickly rises. It is expected that close to 800,000 buffers will be required for 50 nanometer technologies. Thus, it is critical to automate the entire interconnect optimization process to efficiently achieve timing closure.
In addition to timing issues, managing the density of an integrated circuit design is becoming more problematic. The performance of a design highly depends on how packed the logic is geographically in the physical integrated circuit. If the logic is completely spread out, the design is routable but the performance suffers significantly. On the other hand, if the logic is packed, the design is not routable but would yield the best timing characteristics. A packed design is unsuitable for later design changes, such as the insertion of additional logic, such as a synthesized clock tree, since there is no room for the new logic.
Physical synthesis is now prominent in the automated design of blocks for use in high performance processors and Application Specific Integrated Circuits (ASICs). Physical synthesis is the process of concurrently optimizing placement, timing, power consumption, crosstalk effects, and the like, in an integrated circuit design. Physical synthesis helps to eliminate iterations between synthesis and place-and-route. Physical synthesis has the ability to repower gates, insert buffers, clone gates, and the like. Hence, the area of logic in the design remains fluid.
During physical synthesis, buffer insertion is called for to either optimize nets for delay or to fix nets due to electrical violations. One mechanism for performing buffer insertion on a fixed Steiner integrated circuit topology is the van Ginneken algorithm. Van Ginneken's dynamic programming algorithm, described in “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay,” Int'l Symposium on Circuits and Systems, 1990, pp. 865–868, which is hereby incorporated by reference, has become a classic in the field. Given a fixed Steiner tree topology, the van Ginneken algorithm finds the optimal buffer placement on the topology under an Elmore delay model for a single buffer type and simple gate delay model. The primary idea of van Ginneken is to choose a set of buffer candidate locations that lie on the Steiner topology at some uniformly fixed distance apart. Buffer insertion then proceeds for that particular set of candidates from sink to source.
One problem with the van Ginneken approach to buffer insertion is that buffers are inserted at uniformly placed points along a net. That is, there is no consideration for the density of the logic in the vicinity of the candidate point. Thus, buffers may be inserted into regions that are very densely packed with logic or into regions that are sparsely populated with logic, depending on the particular uniform spacing of the candidate points.
In addition, the major weakness of the van Ginneken approach is that it requires a fixed Steiner tree topology that has to be provided in advance. This makes the final buffer solution quality dependent on the input Steiner tree. Even though a particular van Ginneken solution may be optimal for a given topology, the van Ginneken algorithm will yield poor solutions when fed a poor topology. That is, the van Ginneken approach does not take into consideration the physical layout of the environment.
Recent trends toward hierarchical or semi-hierarchical chip design and system-on-chip design force certain regions of a chip to be occupied by large building blocks so that buffer insertion is not permitted in these regions. These constraints on buffer locations can severely hamper solution quality, and these effects need to be considered when optimizing an integrated circuit design.
Finally, the van Ginneken algorithm does not differentiate between critical and non-critical nets. To the contrary, the van Ginneken algorithm treats all nets as having the same criticality and provides a uniform distribution of buffer insertion locations regardless of the actual criticality of the nets. However, in some cases, critical nets should be considered differently from non-critical nets when performing routing and buffer insertion in order to make sure that the delay in the nets is optimized.
Thus, it would be beneficial to have a method and apparatus for generating Steiner trees for routing of nets in an integrated circuit design and performing buffer insertion that takes into account blockage avoidance, delay optimization and design density management.